class Solution {

public:
    struct cmp{
        
        bool operator()(const pair<long,int>& p1,const pair<long,int>& p2) const {
            
            if(p1.first==p2.first){
                return p1.second>p2.second;
            }
            return p1.first>p2.first;
        }
    };
    int x;
    long long sum;
    unordered_map<int,long long> cnt;
    set<pair<long long,int>,cmp> topX;
    set<pair<long long,int>,cmp> other;
    void addItem(int val){

        if(cnt[val]==0){
            return;
        }
        pair<long long,int> item={cnt[val],val};
        if(topX.size()<x){
            topX.insert(item);
            sum+=cnt[val]*val;
        }
        else{
            auto bItem=*topX.rbegin();
            if(cmp{}(item,bItem)){
                sum-=bItem.first*bItem.second;
                sum+=item.first*item.second;
                topX.erase(bItem);
                topX.insert(item);
                other.insert(bItem);
            }
            else{
                other.insert(item);
            }
        }
    }
    void delItem(int val){

        if(cnt[val]==0){
            return ;
        }
        pair<long long,int> item={cnt[val],val};
        if(topX.count(item)){
            topX.erase(item);
            sum-=cnt[val]*val;
        }
        else{
            other.erase(item);
        }  
    }
    void rebalance(){

        while(topX.size()<x && other.size()){
            auto item=*other.begin();
            topX.insert(item);
            sum+=item.first*item.second;
            other.erase(item);
        }
        while(other.size() && topX.size() && cmp{}(*other.begin(),*topX.rbegin())){
            auto oldItem=*topX.rbegin();
            auto newItem=*other.begin();
            topX.erase(oldItem);
            sum-=oldItem.first*oldItem.second;
            topX.insert(newItem);
            sum+=newItem.first*newItem.second;
            other.erase(newItem);   
            other.insert(oldItem);        
        }
    }
    vector<long long> findXSum(vector<int>& nums, int k, int x) {
        
        vector<long long> vecRet;
        this->x=x;
        for(int i=0;i<k;++i){
            ++cnt[nums[i]];
        }
        for(auto& item:cnt){
            addItem(item.first);
        }
        vecRet.push_back(sum);
        for(int i=k;i<nums.size();++i){
            delItem(nums[i-k]);
            --cnt[nums[i-k]];
            addItem(nums[i-k]);
            delItem(nums[i]);
            ++cnt[nums[i]];
            addItem(nums[i]);
            
            rebalance();

            vecRet.push_back(sum);
        }

        return vecRet;
    }
};
